//顺序结构的二叉树

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<math.h>
#define TYPE int
#define NIL 0


typedef struct BinTree
{
	TYPE*  arr;
	size_t cal;//容量
}BinTree;

//创建树
BinTree* creat_tree(size_t cal);
//初始化
void init_tree(BinTree* tree,TYPE* arr,size_t len);
//销毁树
void destory_tree(BinTree* tree);
//清理树
void clear_tree(BinTree* tree);
//高度
size_t high_tree(BinTree* tree);
//密度
size_t density_tree(BinTree* tree);
//树空
bool empty_tree(BinTree* tree);
//访问
TYPE* access_tree(BinTree* tree,size_t level,size_t order);
//双亲 根据值
TYPE* parent_tree(BinTree* tree,TYPE value);
//左孩子
TYPE* lchild_tree(BinTree* tree,TYPE data);
//右孩子
TYPE* rchild_tree(BinTree* tree,TYPE data);
//左兄弟
TYPE*  lbrother_tree(BinTree* tree,TYPE data);
//右兄弟
TYPE* rbrother_tree(BinTree* tree,TYPE data);
//层序遍历
void level_tree(BinTree* tree);
//前序的子函数
void _prev_show(BinTree* tree,size_t i);
//前序
void prev_tree(BinTree* tree);
//中序的子函数
void _in_show(BinTree* tree,size_t i);
//中序
void in_tree(BinTree* tree);
//后序的子函数
void _post_show(BinTree* tree,size_t i);
//后序
void post_tree(BinTree* tree);
//层号遍历
void level_order_tree(BinTree* tree);


int main()
{
	BinTree* tree = creat_tree(256);
	TYPE arr[] = {1,2,3,4,5,6,7,8,9,10};
	init_tree(tree,arr,10);
	level_tree(tree);
//	prev_tree(tree);
//	in_tree(tree);
//	post_tree(tree);
	printf("%d\n",*lchild_tree(tree,4));
	printf("%d\n",*rchild_tree(tree,4));
	printf("%d\n",*lbrother_tree(tree,5));
	printf("%d\n",*rbrother_tree(tree,4));
	printf("%d\n",*parent_tree(tree,2));
	printf("第三行 第二个元素:%d\n",*access_tree(tree,3,2));
	level_order_tree(tree);
	printf("%u\n",density_tree(tree));

}



//创建树
BinTree* creat_tree(size_t cal)
{
	BinTree* tree = malloc(sizeof(BinTree));
	tree->arr = calloc(cal,sizeof(TYPE));
	tree->cal = cal;
	return tree;
}

//初始化
void init_tree(BinTree* tree,TYPE* arr,size_t len)
{
	if(empty_tree(tree))
	{
		memcpy(tree->arr,arr,sizeof(TYPE)* len);	
	}
}
//销毁树
void destory_tree(BinTree* tree);
//清理树
void clear_tree(BinTree* tree);

//高度
size_t high_tree(BinTree* tree)
{
	size_t i=tree->cal;
	while(NIL == tree->arr[--i]);

	size_t high = 0;
	do{
		high++;	
	}while(pow(2,high)-2 <i);
	return high;
	
}
//密度
size_t density_tree(BinTree* tree)
{
	size_t i=tree->cal;
	while(NIL == tree->arr[i]) 	i--;
	return i+1;
}
//树空
bool empty_tree(BinTree* tree)
{
	return 0 == tree->arr[0];	
}
//访问

TYPE* access_tree(BinTree* tree,size_t level,size_t order)
{
	if(pow(2,level-1)<order)return NULL;
	size_t i =pow(2,level-1)+order-2;	
	if(i > tree->cal ) return NULL;
	
	return tree->arr + i;

}
//双亲 根据值
TYPE* parent_tree(BinTree* tree,TYPE value)
{
	if(value == tree->arr[0]) return NULL;
	for(int i=0;i<tree->cal;i++)
	{
	/*	if(tree->arr[i] == value && 0==i%2)
			return tree->arr + (i-1)/2;
		if(tree->arr[i] == value && i%2)
			return tree->arr + i/2;
	*/
		if(tree->arr[i] == value && tree->arr[(i-1)/2])
		{
			return tree->arr+(i-1)/2;	
		}
	
	}

	return NULL;
}
//左孩子
TYPE* lchild_tree(BinTree* tree,TYPE data)
{
	for(int i=0;i<tree->cal;i++)
	{
		if(tree->arr[i]==data && NIL!=tree->arr[i*2+1])
			return tree->arr+i*2+1;
	}
	return NULL;
}
//右孩子
TYPE* rchild_tree(BinTree* tree,TYPE data)
{
	for(int i=0;i<tree->cal;i++)
	{
		if(tree->arr[i]==data && NIL!=tree->arr[i*2+2])
			return tree->arr+i*2+2;
	}
	return NULL;
}
//左兄弟
TYPE*  lbrother_tree(BinTree* tree,TYPE data)
{
	if(tree->arr[0] == data) return NULL;
	//该结点必须是右子结点，下标必须是偶数
	for(int i=0;i<tree->cal;i++)
	{
		if(tree->arr[i] == data && 0 == i%2)	
			return tree->arr + i - 1;
	}
	return NULL;
}
//右兄弟
TYPE* rbrother_tree(BinTree* tree,TYPE data)
{	
	if(tree->arr[0] == data) return NULL;
	//该结点必须是左子结点，下标必须是奇数
	for(int i=0;i<tree->cal;i++)
	{
		if(tree->arr[i] == data && i%2)	
			return tree->arr+i+1;
	}
	return NULL;
}
//层序遍历
void level_tree(BinTree* tree)
{
	for(int i=0;i<tree->cal;i++)
	{
		if(tree->arr[i])
		{
			printf("%d ",tree->arr[i]);	
		}
	}
	printf("\n");
}

//前序遍历的子函数
void _prev_show(BinTree* tree,size_t i)
{
	printf("%d ",tree->arr[i]);
	if(NIL !=tree->arr[i*2+1])
		_prev_show(tree,i*2+1);	
	if(NIL !=tree->arr[i*2+2])
		_prev_show(tree,i*2+2);	

}

//前序
void prev_tree(BinTree* tree)
{	
	printf("前序：");
	_prev_show(tree,0);
	printf("\n");
}
//中序的子函数
void _in_show(BinTree* tree,size_t i)
{
	
	if(NIL !=tree->arr[i*2+1])
		_in_show(tree,i*2+1);
	printf("%d ",tree->arr[i]);
	if(NIL !=tree->arr[i*2+2])
		_in_show(tree,i*2+2);
}


//中序
void in_tree(BinTree* tree)
{
	printf("中序：");
	_in_show(tree,0);
	printf("\n");
}
//后序的子函数
void _post_show(BinTree* tree,size_t i)
{
	if(NIL !=tree->arr[i*2+1])
		_post_show(tree,i*2+1);
	if(NIL !=tree->arr[i*2+2])
		_post_show(tree,i*2+2);
	printf("%d ",tree->arr[i]);
		
}

//后序
void post_tree(BinTree* tree)
{
	printf("后序：");
	_post_show(tree,0);
	printf("\n");
		
}
//层号遍历
void level_order_tree(BinTree* tree)
{
	size_t h=high_tree(tree);
	for(int i=1;i<=h;i++)
	{
		printf("第%d行：",i);
		for(int j=1;j<=pow(2,i-1);j++)	
		{
			printf("%d",*access_tree(tree,i,j));	
		}
		printf("\n");
	}
}
